A thread may add requests to a queue, and another thread may remove requests from the queue. Manipulating a request may require multiple instructions. The queue is a shared resource and a race condition may occur if, for example, a thread attempts to read from the queue while another thread attempts to add a request to the queue. For example, if one thread attempts to read from the queue while another is in the middle of manipulating the queue, the reading thread may find the queue in an inconsistent state. This may result in corruption of the queue.
A common mechanism for ensuring that only one thread manipulates the queue at a time is to provide a locking mechanism for the queue. For example, if a thread attempts to add a request to the queue, the thread first obtains a lock and then safely adds the request to the queue. After adding the request, the thread releases the lock to allow another thread to manipulate the queue. Locking, however, is relatively expensive and can limit scalability. The more locks that are implemented in a system, the more time is spent acquiring and releasing those locks, which is a relatively expensive operation.
Further, an example of a widely used queue is a first-in, first-out (FIFO) queue. In a FIFO queue, data elements inserted before other data elements are removed before the other data elements. Accordingly, a high priority request in a FIFO queue must wait until other requests in the queue have been removed before the high priority request is serviced. This may lead to undesirable results.